package main

// 5. 最长回文子串

//func main() {
//	println(longestPalindrome("cbbd"))
//}

func longestPalindrome(s string) string {
	sLen := len(s)
	if sLen < 2 {
		return s
	}

	arr := make([][]bool, sLen)
	maxLen, begin, tempLen := 1, 0, 0

	for i := range arr {
		arr[i] = make([]bool, len(s))
		arr[i][i] = true
	}

	// 打印动态规划的表格
	for _, bs := range arr {
		println(boolArrToString(bs))
	}

	for j := 1; j < sLen; j++ {
		for i := 0; i < j; i++ {
			//println(i, j, string(s[i]), string(s[j]))
			if s[i] == s[j] {
				if j-i < 2 || arr[i+1][j-1] {
					arr[i][j] = true
					tempLen = j - i + 1
					if tempLen > maxLen {
						maxLen = tempLen
						begin = i
					}
				}
			}
			//println(i, j)
		}
	}
	return s[begin : begin+maxLen]
}
